#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int climbStairs(int n)
    {
        int dp[45] = { 0 };
        dp[0] = 1;
        dp[1] = 2;
        for (int i = 2; i < n; i++)
        {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n - 1];
    }
};


class Solution {
public:
    vector<vector<int>> generate(int numRows)
    {
        vector<vector<int>> ret(numRows);
        int dp[31][31];
        dp[0][0] = 1;
        for (int i = 1; i <= numRows; i++)
        {
            for (int j = 1; j <= i; j++)
            {
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
                ret[i - 1].push_back(dp[i][j]);
            }
        }

        return ret;
    }
};


class Solution {
public:
    int rob(vector<int>& nums)
    {
        int dp[101] = { 0 };
        dp[1] = nums[0];
        int n = nums.size();
        for (int i = 2; i <= n; i++)
        {
            dp[i] = max(dp[i - 2] + nums[i - 1], dp[i - 1]);
        }

        return dp[n];
    }
};


class Solution {
public:
    int numSquares(int n)
    {
        int e = sqrt(n);
        vector<vector<int>> dp(e + 1, vector<int>(n + 1, INT_MAX));
        dp[0][0] = 0;
        for (int i = 1; i <= e; i++)
            for (int j = 0; j <= n; j++)
            {
                dp[i][j] = dp[i - 1][j];
                if (j >= i * i) dp[i][j] = min(dp[i][j], dp[i][j - i * i] + 1);
            }


        return dp[e][n] == INT_MAX ? -1 : dp[e][n];
    }

};